#include <string.h>
#include <stdlib.h>
#include <stdio.h>
int strStr(char *haystack, char *needle){
    int hLen = strlen(haystack), nLen = strlen(needle);
    if (nLen == 0){
        return 0;
    }
    int *pi = malloc(sizeof(*pi) * nLen);
    memset(pi , 0, sizeof(*pi) * nLen);
    for(int i = 1, j = 0; i < nLen; i++){
        while(j > 0 && needle[i] != needle[j]){
           j = pi[j - 1]; 
        }
        if (needle[i] == needle[j])
            j++;
        pi[i] = j;
    }

    for(int i = 0, j = 0; i < hLen; i++){
        //mov index j
        while(j > 0 && needle[j] != haystack[i]){
            j = pi[j - 1];
        }
        if (needle[j] == haystack[i])
            j++;
        if (j == nLen){
            return i - nLen + 1;
        }
    }

    free(pi);
    return -1;
}